社会をつなぐ見えない糸を、どのように数学的に記述できるでしょうか？たとえば、 ベイコン・ナンバー ベラ・ルゴシからハリウッドのアイコンまでを結ぶものや、 類似性グラフ 近接度に基づいてデータポイントをクラスタリングするような、 グラフ理論 グラフ理論は、これらの離散的な世界をモデル化するための形式的言語 $G = (V, E)$ を提供します。
1. グラフの構造
本質的には、グラフとは 頂点 ($V$) と、 辺 ($E$) で構成されています。ただし、ルールは構造によって異なります：
- 単純グラフ： 最も洗練された形であり、 ループ （頂点が自分自身に接続する辺）と、 並行辺 （同じ2つの頂点間の重複した辺）を禁止しています。
- 多重グラフ： ループと並行辺を許容し、同じ2つのノード間での複数種類の相互作用（例：テキスト通話対比）をモデル化する際によく使われます。
- 孤立頂点： 頂点 $v$ がその上に接続する辺がない場合、それは孤立頂点と呼ばれ、現在のセットでは関係を持たないオブジェクトを表します。
近接性の論理
データサイエンスでは、しばしば 不相似関数 を使ってグラフを構築します：
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
$v$ と $w$ の間に辺を引くのは、$s(v, w)$ が特定のしきい値以下の場合に限られます。これにより、『隣人』ネットワークが効果的に構築されます。
2. パス、連結性、および成分
ある パス は頂点と辺の順列です。もしパスが一度も同じ頂点を訪れないならば、それは 単純パスと呼ばれます。連結性はグラフの生命線です：
- 連結グラフ： すべての頂点ペア間には すべての 頂点ペア間のパスが存在します。
- 成分： グラフが連結でない場合、互いに分離した部分に分割され、それらを成分と呼びます。各成分は最大の連結部分グラフです。
3. 部分グラフ：集合の構造
部分グラフ $G' = (V', E')$ とは、$V'$ のすべての頂点が $V$ に含まれ、$E'$ のすべての辺が $V'$ に含まれる頂点を接続するような、グラフ $G$ の部分集合です。部分グラフを特定することは、グローバルなネットワーク内の局所パターンを検出するために極めて重要です。
🎯 核心原理：握手補題
任意の無向グラフにおいて、すべての頂点の次数の合計は辺の数の2倍になります。これは、奇数の次数を持つ頂点の数が偶数であることを意味します。
$$\sum_{v \in V} \text{deg}(v) = 2|E|$$